package com.mango.leet.code.hard;

/**
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 *
 * 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
 *
 *  
 *
 * 示例：
 *
 *
 * 输入：root = [1,2,3,null,null,4,5]
 * 输出：[1,2,3,null,null,4,5]
 *  
 *
 * 注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.*;

/**
 * 剑指 Offer 37. 序列化二叉树
 * @Author: mango
 * @Date: 2022/4/15 10:31 下午
 */
public class LCoffer_37 {
    /**
     * Definition for a binary tree node.
     */ public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
     }

    public class Codec {

        // 前序遍历序列化
        public String serialize(TreeNode root) {
            return preOrderEn(root);
        }
        // 前序遍历，E为结尾符，#为空节点
        private String preOrderEn(TreeNode root) {
            if(root == null){
                return "#E";
            }
            String result = root.val + "E";
            result += preOrderEn(root.left);
            result += preOrderEn(root.right);
            return result;
        }


        // 前序遍历反序列化
        public TreeNode deserialize(String data) {
            //1E2E#E#E3E4E#E#E5E#E#E
            String[] arr = data.split("E");
            if(arr.length == 0){
                return null;
            }
            Queue<String> queue = new LinkedList<>();
            for(String str : arr){
                queue.offer(str);
            }
            return preOrderDe(queue);
        }
        // 前序遍历
        private TreeNode preOrderDe(Queue<String> queue) {
            String val = queue.poll();
            // 遇到#号，则返回null
            if("#".equals(val)){
                return null;
            }
            // 在前序的位置，组装节点
            TreeNode root = new TreeNode(Integer.valueOf(val));
            // 左节点
            root.left = preOrderDe(queue);
            // 右节点
            root.right = preOrderDe(queue);
            return root;
        }


    }

}
